#define _CRT_SECURE_NO_WARNINGS 1

//https://www.acwing.com/problem/content/94/
//92. 递归实现指数型枚举
//从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。
//数据范围
//1≤n≤15
//输入样例：
//3
//输出样例：
//
//3
//2
//2 3
//1
//1 3
//1 2
//1 2 3
//
//#include<iostream>
//const int N = 20;
//int n;
//int st[N];		//0表示当前数字未选，1表示已选，2表示不选
//
//void dfs(int x)
//{
//	if (x > n)						//走完打印退出
//	{
//		for (int i = 1; i <= n; i++)
//		{
//			if(st[i]==1)
//				printf("%d ",i);
//		}
//		printf("\n");
//		return;
//	}
//	//不选
//	st[x] = 2;
//	dfs(x + 1);
//	st[x] = 0;	//回溯到保护现场（退出栈帧到上一个未选dfs）
//	//选
//	st[x] = 1;
//	dfs(x + 1);
//	st[x] = 0;
//}
//
//
//int main()
//{
//	scanf("%d", &n);
//	dfs(1);
//	return 0;
//}


//https://www.acwing.com/problem/content/96/
//94. 递归实现排列型枚举
//把 1∼n这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。
//输入格式
//一个整数 n。
//
//输出格式
//按照从小到大的顺序输出所有方案，每行 1个。
//首先，同一行相邻两个数用一个空格隔开。
//其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
//数据范围
//1≤n≤9
//输入样例：
//3
//输出样例：
//1 2 3
//1 3 2
//2 1 3
//2 3 1
//3 1 2
//3 2 1
//字典序
//#include<iostream>
//
//const int N = 20;
//bool st[N];			//默认false，当前数字没被选过
//int arr[N];			//存放数字
//int n;
//
//void dfs(int x)
//{
//	if (x > n)
//	{
//		for (int i = 1; i <= n; i++)
//		{
//			printf("%d ", arr[i]);
//		}
//		printf("\n");
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (!st[i])
//		{
//			st[i] = true;	//当前数字被选为true
//			arr[x] = i;		//存入当前数字
//			dfs(x + 1);		//跳到下一个位置  _  _  _
//			st[i] = false;	//回溯
//			arr[x] = 0;
//		}
//	}
//}
//
//
//int main()
//{
//	scanf("%d", &n);
//	dfs(1);
//	return 0;
//}

//
//P1157组合的输出
//https ://www.luogu.com.cn/problem/P1157
//排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且 r ≤n)，我们可以简单地将n个元素理解为自然数1, 2, …, n从中任取r个数。
//
//现要求你输出所有组合。
//
//例如n = 5, r = 3所有组合为：
//
//1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5, 2 3 4, 2 3 5, 2 4 5, 3 4 5

//#include<iostream>
//const int N = 20;
//int n, r;
//int arr[N];
//
//void dfs(int x, int start)
//{
//	//剪枝
//	if ((x - 1) + n - start + 1 < r)
//		return;
//	if (x > r)
//	{
//		for (int i = 1; i <= r; i++)
//		{
//			printf("%3d", arr[i]);
//		}
//		printf("\n");
//		return;
//	}
//
//	for (int i = start; i <= n; i++)
//	{
//		arr[x] = i;
//		dfs(x + 1, i + 1);
//		arr[x] = 0;
//	}
//}
//
//int main()
//{
//	scanf("%d%d", &n, &r);
//	dfs(1, 1);
//	return 0;
//}


//https://www.luogu.com.cn/problem/P1036
// P1036 [NOIP2002 普及组] 选数
//已知 n 个整数 x1, x2, …, xn，以及11个整数 k(k < n)。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n = 4, k = 3, 4个整数分别为3, 7, 12, 19时，可得全部的组合与它们的和为：
//
//	3 + 7 + 12 = 22
//
//	3 + 7 + 19 = 29
//
//	7 + 12 + 19 = 38
//
//	3 + 12 + 19 = 34
//
//	现在，要求你计算出和为素数共有多少种。
//
//	例如上例，只有一种的和为素数：3 + 7 + 19 = 29。
//
//	输入格式
//
//	键盘输入，格式为：
//
//	n, k(1 <= n <= 20, k < n)
//	x1, x2, …, xn(1 <= xi <= 5000000)
//
//	输出格式
//
//	屏幕输出，格式为： 1个整数（满足条件的种数）。

//思路：组合后相加判断素数
#include<iostream>
const int N = 30;
int n, k;
int arr[N];	//存储数组
int q[N];	//输入数组
int res;

bool is_prime(int sum)
{
	if (sum < 2)
		return false;
	for (int i = 2; i < sum / i; i++)
	{
		if (sum % i == 0)
		{
			return false;
		}
	}
	return true;
}

void dfs(int x, int start)
{
	//剪枝
	if ((x - 1) + n - start + 1 < k)	//可选择数字不满足k个
	{
		return;
	}
	if (x > k)
	{
		int sum = 0;
		for (int i = 1; i <= k; i++)
		{
			sum += arr[i];
		}
		if (is_prime(sum))
			res++;
		return;
	}
	for (int i = start; i <= n; i++)
	{
		arr[x] = q[i];
		dfs(x + 1, i + 1);
		arr[x] = 0;
	}
}

int main()
{
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &q[i]);
	}
	dfs(1, 1);
	printf("%d", res);
	return 0;
}